\documentclass[a4paper]{article}
\title{Advanced Cryptography Coursework}
\author{Joseph Hallett}
\date\today

\usepackage{url}
\usepackage{listings}

\usepackage{mathspec}
\usepackage{xltxtra}
\defaultfontfeatures{Scale=MatchLowercase}
\setmainfont{Palatino}
\setmathsfont(Digits,Latin,Greek)[]{Palatino}
\setallsansfonts{Optima}
\setallmonofonts{Menlo}

\lstset{
  basicstyle=\sf,
  columns=fullflexible
  }

\frenchspacing


\begin{document}
\maketitle

\section{Description of attack}

James Manger's chosen cipher text attack works because the decryption
program leaks information when attempting to decipher ciphers.
Specifically there are two interesting errors that can occur when
decrypting a text. Being able to tell them apart reveals whether your
text was too big, or failed an integrity check (i.e. was the right sized
but the encoding failed to decode).

Manger's attack has three steps. The first finds a range in which the
message can be found. The second refines that range. The third does a
binary search to find the exact message. In each step it uses two errors
to decide what to do next.

\section{Applicability and prevention of the attack}

The key to the attack is being able to tell apart the two errors. In a
real implementation of the attack you're not going to have a nice oracle
which tells you exactly why a decryption failed.

Realistically the attack is performed via a side
channel. Looking at the OpenSSL implementation\footnote{
\url{http://www.opensource.apple.com/source/OpenSSL/OpenSSL-23/openssl/c%
rypto/rsa/rsa_oaep.c}} the first of the two errors is detected early
in the decryption process step. If an attacker were to be looking
closely at the timing of the program they might notice that under
certain conditions the program sometimes crashes earlier with certain
texts rather than others.

Reasoning in this way, and with the aid of the source code they might
be able to deduce that a quick crash is symptomatic of error one, and
a slow crash is symptomatic of error two. The larger the gap in timing
between these two errors the easier it will be.

The OpenSSL developers approach to this is that even after the error has
been detected to continue on and set a flag so that later they can crash
at around the same time as they would have detected the other error
had it been present. The relevant code is shown in Figures \ref{fig:1}
and \ref{fig:2}. This helps resist the timing attack as the work done
between the sections is significant.

\begin{figure}[!ht]
  \begin{center}
    \begin{lstlisting}[language=c]
if (lzero < 0)
    {
    /* lzero == -1 */
    
    /* signalling this error immediately after detection might allow
     * for side-channel attacks (e.g. timing if 'plen' is huge
     * -- cf. James H. Manger, "A Chosen Ciphertext Attack on RSA Optimal
     * Asymmetric Encryption Padding (OAEP) [...]", CRYPTO 2001),
     * so we use a 'bad' flag */
    bad = 1;
    lzero = 0;
    }
\end{lstlisting}
  \end{center}
  \caption{Detection of the first error, and setting of the bad flag in the OpenSSL RSA OAEP source code}
  \label{fig:1}
\end{figure}

\begin{figure}[!ht]
  \begin{center}
    \begin{lstlisting}[language=c]
if (memcmp(db, phash, SHA_DIGEST_LENGTH) != 0 || bad)
    goto decoding_err;
	    \end{lstlisting}
  \end{center}
  \caption{Detection of the second error and delayed handling of the first error in the OpenSSL RSA OAEP source code}
  \label{fig:2}
\end{figure}

\section{Efficiency of the attack}

The attack requires you run an RSA oracle repeatedly. On an unoptimised
attack written in C against a 1024 bit RSA-key takes around fifteen
seconds on a home PC. Increasing the size of the key will slow down the
attack significantly as the space to search becomes larger.  


\end{document}

